import com.sun.scenario.effect.Brightpass;

import java.util.Arrays;

public class Sort {

    public static void swop(int[] array, int i, int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

    public static int quickSortHoare(int[] array, int left, int right) {
        int key_i = left;
        int key = array[left];
        while (left < right) {
            while (left < right && array[right] >= key) {
                right--;
            }
            while (left < right && array[left] <= key) {
                left++;
            }
            swop(array, left, right);
        }
        swop(array, key_i, left);
        return left;
    }

    public static void quickSortHelper(int[] array, int left, int right) {

        // 但遍历对象为逆序时，right 与 pivot 重合， 此时left承接pivot + 1就有可能大于right
        // 所以此处 递归的尽头，二叉树结构的末端，left和right的重合，在代码上有可能left会大于right
        if (right <= left) {
            return;
        }
        int pivot = quickSortHoare(array, left, right);

        quickSortHelper(array, left, pivot);
        quickSortHelper(array, pivot + 1, right);
    }

    public static void quickSort(int[] array) {
        quickSortHelper(array, 0, array.length - 1);
    }

    public static void main(String[] args) {
        int[] array = {12, 6, 42, 22, 28, 12, 3, 16, 30};
        quickSort(array);
        System.out.println(Arrays.toString(array));
    }
}
